Méthodes de Monte Carlo

2. Prédiction : Estimation de la fonction des valeurs des états

Nous commençons par considérer les méthodes de Monte Carlo dans le but d'apprendre la fonction des valeurs d'états d'une stratégie. Souvenez-vous que la valeur d'un état est la valeur moyenne du revenu que l'agent perçoit à partir de cet état. Une manière simple d'estimer cette valeur à partir de résultats obtenus d'une expérience est donc de simplement calculer la valeur moyenne des revenus observés après chaque visite de cet état. Plus on observera de revenus, plus la moyenne sera précise. C'est l'idée des méthodes de Monte Carlo.

2.1 Méthodes FVMC et EVMC

Supposons que nous souhaitions estimer $V_\pi(s)$, la valeur d'un état $s$ en suivant une stratégie $\pi$, compte tenu d'un ensemble d'épisodes obtenus en suivant la stratégie $\pi$ et qui passe par $s$. Chaque occurrence de l'état $s$ dans un épisode est appelée une visite de $s$. Bien sûr, $s$ peut être visité plusieurs fois au cours d'un même épisode. La première fois où l'état $s$ est visité est appelée la première visite (first visit) de $s$.

La méthode FVMC (First-Visit Monte Carlo) estime $V_\pi(s)$ en moyennant les revenus qui suivent la première visite de l'état $s$, alors que la méthode EVMC (Every-Visit Monte Carlo) fait la moyenne à partir des revenus qui suivent toutes les visites de l'état $s$.

Ces deux méthodes convergent vers $V_\pi(s)$ lorsque le nombre de visites tend vers l'infini. L'écart type tend vers $1/\sqrt(n)$ où n est le nombre de revenus moyennés.

2.2. Algorithme FVMC

2.3. Algorithme EVMC